package com.yiwenup.leetcode.hot;

/**
 * https://leetcode-cn.com/problems/counting-bits/
 **/
public class No0338 {

    /**
     * 执行用时：1 ms, 在所有 Java 提交中击败了99.92%的用户
     * 内存消耗：45.3 MB, 在所有 Java 提交中击败了18.75%的用户
     */
    public int[] countBits(int n) {
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            res[i] = Integer.bitCount(i);
        }

        return res;
    }

    /**
     * 执行用时：2 ms, 在所有 Java 提交中击败了42.22%的用户
     * 内存消耗：45.1 MB, 在所有 Java 提交中击败了26.46%的用户
     */
    public int[] countBits2(int n) {
        int[] res = new int[n + 1];
        for (int i = 0; i <= n; i++) {
            res[i] = counter(i);
        }
        return res;
    }

    private int counter(int num) {
        int count = 0;
        while (num > 0) {
            num &= (num - 1);
            count++;
        }
        return count;
    }
}
